package com.whosly.demo.benchmark.sortalgorithms.heap;

import com.whosly.demo.benchmark.sortalgorithms.ISortingAlgorithms;

/**
 * 堆排序（Heap Sort）
 *
 * @author fengyang
 * @date 2023/6/13 上午11:35
 * @see <a href="fengyang@stoneatom.com">mailTo: fengyang@stoneatom.com</a>
 */
public class HeapSort implements ISortingAlgorithms
{
    private int heapLen;

    public HeapSort()
    {
        this.heapLen = 0;
    }

    @Override
    public int[] sorting(int[] arr)
    {
        heapLen = arr.length;
        for (int i = heapLen - 1; i >= 0; i--) {
            heapify(arr, i);
        }

        for (int i = heapLen - 1; i > 0; i--) {
            swap(arr, 0, heapLen - 1);
            heapLen--;
            heapify(arr, 0);
        }

        return arr;
    }

    private void heapify(int[] arr, int idx) {
        int left = idx * 2 + 1, right = idx * 2 + 2, largest = idx;
        if (left < heapLen && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heapLen && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != idx) {
            swap(arr, largest, idx);
            heapify(arr, largest);
        }
    }

    private void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
}
